package com.laotang.第_10_章_二叉搜索树.力扣_173_二叉搜索树迭代器;

import com.laotang.第_10_章_二叉搜索树.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class _173_binary_search_tree_iterator {

}

class BSTIterator1 {

    private List<Integer> list = new ArrayList<>();
    private int idx = 0;

    public BSTIterator1(TreeNode root) {
        inOrder(root);
    }

    private void inOrder(TreeNode node) {
        if (node == null) return;

        inOrder(node.left);
        list.add(node.val);
        inOrder(node.right);
    }

    /** @return the next smallest number */
    public int next() {
        return list.get(idx++);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return idx < list.size();
    }
}


class BSTIterator {

    private TreeNode curr;
    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        curr = root;
    }

    /** @return the next smallest number */
    /*
     每次调用 next()函数最坏情况下需要 O(n)的时间；
     但考虑到 n 次调用 next() 函数总共会遍历全部的 n 个节点，
     因此总的时间复杂度为 O(n)，因此单次调用平均下来的均摊复杂度为 O(1)
     */
    public int next() {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        int res = curr.val;
        curr = curr.right;
        return res;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return curr != null || !stack.isEmpty();
    }
}
